1. Technical Field
The present invention relates generally to routing paths through polygonal objects. Particularly, the present invention relates to a method, system and computer program product for determining a non-intersecting path between two points, given a field of obstacles.
2. Description of Related Art
Finding the shortest, non-intersecting path between two points, given a field of obstacles, is a typical problem solved in many applications including manufacturing, robot motion planning and software design tools. An obstacle is a polygonal object to be avoided during the routing of a path. A polygonal object is a closed plane figure bounded by straight lines. Typically, a path is a line between two endpoints, the origin and the destination. The line is generated by routing the path according to certain goals. The path's route will consist of one or more straight-line segments. A segment is a straight line between points. Each point is either a vertex or an endpoint of a path. A vertex is one of the four corners of an obstacle.
However, the result of applying existing algorithms repeatedly to multiple paths in the same field of obstacles is often unacceptable and causes many problems. For example, several paths may converge at the same point, making it difficult to distinguish the original paths from each other.
Previous solutions for finding the shortest, non-intersecting path between two points, given a field of obstacles, begin with developing a reduced visibility graph of the obstacles and then determining the shortest path between two endpoints using Dijkstra's algorithm, which is well known in the field. In the case of multiple paths, the paths are offset from the obstacles and other paths. This means, however, that the paths no longer directly travel their computed shortest path from the reduced visibility graph. This gives rise to two major problems.
First, the offset paths may no longer be clear of intersections. The path has changed from what was originally computed and may now intersect new obstacles. It is therefore necessary to check the new offset line segments against intersections and compute a new solution. However, this can have a cascading effect as each new solution may encounter new obstacles and it may be necessary to repeat the check several times. Also, not only can new obstacles continue to intersect the modified lines, but the offset lines themselves may intersect each other, again causing new solutions to be calculated.
The second problem occurs when paths intersect multiple common vertices. In such a case, if the vertices are not ordered correctly, unnecessary crossed paths can occur.
Both of these problems are daunting and expensive, in terms of CPU usage, manpower, and overhead, to overcome. The conventional approach is to compare each path's vertex to every other path which goes through the same vertex. Often this comparison is not useful. Additionally, it is necessary to walk all the paths until a meaningful comparison can be made, which takes significant time and resources.
Therefore, it would be advantageous to have an improved method, system and computer program product for determining a non-intersecting path between two points, given a field of obstacles.